#include <stdio.h>      // 提供输入输出函数，如 printf、fgets
#include <string.h>     // 提供字符串处理函数，如 strcmp、strlen、strcpy、strtok
#include <ctype.h>      // 提供字符处理函数，如 isalpha
#include <stdlib.h>     // 提供动态内存分配函数，如 malloc、free、qsort

#define MAX_WORDS 1000               // 最多单词数量
#define MAX_WORD_LENGTH 21           // 单词最大长度（含'\0'）
#define MAX_SENTENCE_LENGTH 10001    // 输入句子最大长度

// step 1# 字典序排序比较函数
int compare(const void *a, const void *b) {
    return strcmp(*(const char **)a, *(const char **)b);  // 按字典序比较两个字符串
}

// step 2# 判断一个字符串是否为合法英文单词（全为字母且长度 ≥ 2）
int isValidWord(const char *word) {
    int len = strlen(word);         // 获取单词长度
    if (len < 2) return 0;          // 长度小于2则非法
    for (int i = 0; i < len; i++) {
        if (!isalpha(word[i]))     // 只要有非字母字符就非法
            return 0;
    }
    return 1;
}

// step 3# 判断 word 是否已存在于 words 数组中（用于去重）
int isDuplicate(char *word, char **words, int count) {
    for (int i = 0; i < count; i++) {
        if (strcmp(word, words[i]) == 0)  // 若存在相同字符串，说明重复
            return 1;
    }
    return 0;
}

int main() {
    // step 4# 读取输入的句子和前缀
    char sentence[MAX_SENTENCE_LENGTH], prefix[MAX_WORD_LENGTH];  // 存储句子和前缀
    fgets(sentence, MAX_SENTENCE_LENGTH, stdin);  // 读取句子
    fgets(prefix, MAX_WORD_LENGTH, stdin);        // 读取前缀

    // step 5# 去除前缀末尾的换行符
    size_t prefix_len = strlen(prefix);       
    if (prefix[prefix_len - 1] == '\n') {
        prefix[prefix_len - 1] = '\0';     // 将换行替换为字符串结束符
        prefix_len--;
    }

    // step 6# 将句子中所有非字母字符替换为空格（便于后续分词）
    for (int i = 0; sentence[i]; i++) {
        if (!isalpha(sentence[i])) {
            sentence[i] = ' ';             // 标点、空格、数字等都统一为空格
        }
    }

    // step 7# 分词：用空格分割单词并去重，保存在 words 数组中
    char *words[MAX_WORDS];       // 用于保存所有合法、去重后的单词
    int word_count = 0;           // 实际保存的单词数

    char *token = strtok(sentence, " ");   // 使用 strtok 分割单词
    while (token != NULL) {
        if (isValidWord(token) && !isDuplicate(token, words, word_count)) {
            words[word_count] = (char *)malloc(strlen(token) + 1);  // 动态分配空间
            strcpy(words[word_count], token);                       // 拷贝内容
            word_count++;
        }
        token = strtok(NULL, " ");
    }

    // step 8# 对所有单词进行字典序排序
    qsort(words, word_count, sizeof(char *), compare);

    // step 9# 查找所有匹配前缀的单词并输出（若有多个以空格分隔）
    int found = 0;  // 是否找到匹配单词标志
    for (int i = 0; i < word_count; i++) {
        if (strncmp(words[i], prefix, prefix_len) == 0) {  // 前缀匹配
            if (found > 0) printf(" ");     // 控制多个单词之间空格
            printf("%s", words[i]);
            found++;
        }
        free(words[i]);  // 释放之前 malloc 的空间
    }

    // step 10# 若没有匹配，输出原前缀
    if (!found) {
        printf("%s", prefix);
    }

    printf("\n");
    return 0;
}
